﻿using System.Collections.Generic;
using System.Linq;


namespace QSharp.Scheme.Classical.Graphs
{
    public static class ShortestPath
    {
        public interface IDistanceIndicator
        {
            IDistance GetMaximalDistance();

            IDistance GetCurrentDistanceFromSource(IVertex v);
            void UpdateDistanceFromSource(IVertex v, IDistance d);

            void UpdateConnectivity(IVertex source, IVertex target);
        }
    }

    public static class ShortestPathFordFulkerson
    {
        public interface IVertexSet<out TG>
            where TG : IGetIncidentalVertices, IGetWeight
        {
            TG Graph { get; }

            bool IsEmpty();
            IVertex Pop();
            void Push(IVertex v);
        }

        public static void Calculate<TG>(IVertexSet<TG> q, ShortestPath.IDistanceIndicator r)
            where TG : IGetIncidentalVertices, IGetWeight
        {
            var g = q.Graph;

            while (!q.IsEmpty())
            {
                var v = q.Pop();

                var incidental = g.GetIncidentalVertices(v);

                foreach (var i in incidental)
                {
                    var distSV = r.GetCurrentDistanceFromSource(v);
                    var distSVI = distSV.Add(g.GetWeight(v, i));
                    var distSI = r.GetCurrentDistanceFromSource(i);

                    if (distSVI.CompareTo(distSI) >= 0) continue;

                    r.UpdateDistanceFromSource(i, distSVI);
                    r.UpdateConnectivity(v, i);
                    q.Push(i);
                }
            }
        }
    }

    public static class ShortestPathDijkstra
    {
        public interface IVertexCollector
        {
            IGetWeight Graph { get; }

            bool IsComplete();
            
            IEnumerable<IVertex> GetAllPreviouslyAdded();
            IEnumerable<IVertex> GetAllAlienNeighbours(IVertex v);
            IEnumerable<IVertex> GetAllYetToBePickedUp();

            void ClearAllAddedInThisRound();
            void Add(IVertex o);
            void AddMore(IVertex o);
            void Update();
        }

        /**
         * <Summary>
         *  `s' is the vertex to which the distances from all 
         *    the other vertices in the graph are calculated.
         *  `g' is the graph containing `s'
         *  `treesize' is to be initialized and associated with `g'
         *  `r' is initialized empty
         * </Summary>
         */
        public static void Calculate(IVertexCollector c, ShortestPath.IDistanceIndicator r)
        {
            /** 
             * <remarks>
             *  one may not implement this routine at all
             *  as long as proper initialization of `c' 
             *  with respect to `g' (or the actual underlying graph)
             *  and `s' is ensured
             * </remarks>
             */

            var g = c.Graph;

            while (!c.IsComplete())
            {
                var previouslyAdded = c.GetAllPreviouslyAdded();
                foreach (var prev in previouslyAdded)
                {
                    var neighbors = c.GetAllAlienNeighbours(prev);
                    foreach (var n in neighbors)
                    {
                        var d = r.GetCurrentDistanceFromSource(prev);
                        /** 
                         * <remarks>
                         *  In the rare case that a null distance is defined to represent
                         *  infinity (or inaccessibility), we need to enable the code below.
                         *  This applies to the similar one that closely follows.
                         * </remarks>
                         */
#if NEVER
                        if (d == null)
                            continue;
#endif
                        var w = g.GetWeight(prev, n);
                        /** 
                         * <remarks>
                         *  Either r.GetCurrentDistanceFromSource or d.Add should create a new
                         *  IDistance object.
                         *  That is, if GetCurrentDistanceFromSource doesn't make a copy of
                         *  IDistance according to its internal record, d.Add should add 
                         *  d to w and return the result as a newly created IDistance
                         * </remarks>
                         */
                        d = d.Add(w);

                        if (d.CompareTo(r.GetCurrentDistanceFromSource(n)) < 0)
                        {
                            /**
                             * <remarks>
                             *  The UpdateConnectivity method is used to outline the 
                             *  shortest path in the result which is a tree with `s' as root.
                             *  The method updates treesize's parent (which may be assigned in previous
                             *  phases) to `prev'.
                             * </remarks>
                             */
                            r.UpdateConnectivity(prev, n);
                            r.UpdateDistanceFromSource(n, d);
                        }
                    }
                }

                var min = r.GetMaximalDistance();
                /**
                 * <remarks>
                 *  Important: It is GetAllYetToBePickedUp's duty to clear 
                 *  the temporary set (composed of newly added vertices)
                 * </remarks>
                 */
                var allToBePickedup = c.GetAllYetToBePickedUp();
                foreach (var outsider in allToBePickedup)
                {
                    var dist = r.GetCurrentDistanceFromSource(outsider);
#if NEVER
                    if (dist == null)
                        continue;
#endif
                    var cmp = dist.CompareTo(min);
                    if (cmp < 0)
                    {
                        min = dist;
                        c.ClearAllAddedInThisRound();
                        /**
                         * <remraks>
                         *  c.Add should make a copy of outsider before adding it
                         *  to its inner list, since outsider is a reference object
                         *  and may be changed elsewhere, most probably for example,
                         *  in the enumerator inside `allToBePickedup'
                         * </remarks>
                         */
                        c.Add(outsider);
                    }
                    else if (cmp == 0)
                    {
                        /**
                         * <remraks>
                         *  The user might as well leave the implementation of
                         *  this method blank if she thinks having only one `prev'
                         *  processed per round is acceptable.
                         * </remarks>
                         */
                        c.AddMore(outsider);
                    }
                }
                /**
                 * <remarks>
                 *  c.Update has two duties:
                 *   one is obvious, it copies all nuser
                 *   ewly added vertices to 
                 *   the set of concluded vertices;
                 *   the other is easy to overlook but rather crucial, it should
                 *   reevaluate the completeness based on whether there is 
                 *   newly added vertices
                 * </remarks>
                 */
                c.Update();
            }
        }
    }   /* class ShortestPathDijkstra */

    public class ShortestPathFloydWarshall
    {
        public interface IRoutingTable
        {
            void SetDistance(IVertex s, IVertex t, IDistance d);
            IDistance GetDistance(IVertex s, IVertex t);

            /**
             * <summary>
             *  `v' is a vertex on current path from s to t 
             * </summary>
             */
            void SetRoute(IVertex s, IVertex t, IVertex v);
        }

        /**
         * <remarks>
         *  Cases dealing with same source and target node can be wiped out
         *  but it is not very necessary and demanding equatability of vertex
         * </remarks>
         */
        public static void Calculate<TG>(TG g, IRoutingTable r)
            where TG : IGetAllVertices, IGetWeight
        {
            var vertices = g.GetAllVertices();

            // To avoid multiple enumeration
            var enumerable = vertices as IList<IVertex> ?? vertices.ToList();

            // initialize the distance table
            foreach (var v in enumerable)
            {
                foreach (var w in enumerable)
                {
                    r.SetDistance(v, w, g.GetWeight(v, w));
                }
            }

            foreach (var u in enumerable)
            {
                foreach (var v in enumerable)
                {
                    foreach (var w in enumerable)
                    {
                        /*
                         * <remarks>
                         *  Here it also requires either r.GetDistance()
                         *  or dvu.Add() returns a newly created distance
                         *  object that can be used by succeeding distance
                         *  setting;
                         *  It may be SetRoute's duty to create a copy of `u'
                         * </remarks>
                         */

                        var dvu = r.GetDistance(v, u);
                        var duw = r.GetDistance(u, w);

                        if (dvu.IsInfinity() || duw.IsInfinity())
                            continue;

                        var dvw = r.GetDistance(v, w);
                        var dvuw = dvu.Add(duw);

                        if (dvw.IsInfinity() || dvuw.CompareTo(dvw) < 0)
                        {
                            r.SetDistance(v, w, dvuw);
                            r.SetRoute(v, w, u);
                        }
                    }
                }
            }
        }
    }
}
